矩阵的 LU 分解

什么是 LU 分解

我们知道，含有多个未知数的唯一解线性方程组（形如 $A x = b$ ）直接解起来非常麻烦和困难，为了简化计算，可以将系数矩阵 $A$ 分解为下三角矩阵和上三角矩阵的乘积 $L U$ ，即：

A = L U

这样，就可以先求解方程组

L y = b

得到中间解 $y$ ，再代入

U x = y

求解 $x$ ，即为原方程组的解。

由于 $L$ 和 $U$ 都是三角矩阵，所以计算 $y$ 和 $x$ 时可以逐个求出各分量（解出一个分量后就可以代入用于计算下一个分量，从而得到完整的解），这对于计算机来说是高效的计算方法。

一个实际例子

有唯一解的线性方程组：

{\begin{matrix} 4 x_{1} & + 2 x_{2} & + 1 x_{3} & + 5 x_{4} & = 1 \\ 8 x_{1} & + 7 x_{2} & + 5 x_{3} & + 10 x_{4} & = 1 \\ 4 x_{1} & + 8 x_{2} & + 3 x_{3} & + 6 x_{4} & = 1 \\ 6 x_{1} & + 8 x_{2} & + 4 x_{3} & + 9 x_{4} & = 1 \end{matrix}

表示为 $A x = b$ 的矩阵形式：

A = [\begin{matrix} 4 & 2 & 1 & 5 \\ 8 & 7 & 5 & 10 \\ 4 & 8 & 3 & 6 \\ 6 & 8 & 4 & 9 \end{matrix}], b = [\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \end{matrix}]

变换为 $A = L U$ 形式：

A = [\begin{matrix} 4 & 2 & 1 & 5 \\ 8 & 7 & 5 & 10 \\ 4 & 8 & 3 & 6 \\ 6 & 8 & 4 & 9 \end{matrix}] = \underset{L}{[\begin{matrix} 1 \\ 2 & 1 \\ 1 & 2 & 1 \\ \frac{3}{2} & \frac{5}{3} & \frac{5}{4} & 1 \end{matrix}]} \underset{U}{[\begin{matrix} 4 & 2 & 1 & 5 \\ 3 & 0 & 0 \\ 2 & 1 \\ \frac{1}{4} \end{matrix}]}

再按照 $L y = b$ ， $U x = y$ 的顺序求解即可。

紧凑格式

上文中 $L$ 和 $U$ 的紧凑格式为：

(L | U) = [\begin{matrix} 4 & 2 & 1 & 5 \\ 2 & 3 & 0 & 0 \\ 1 & 2 & 2 & 1 \\ \frac{3}{2} & \frac{5}{3} & \frac{5}{4} & \frac{1}{4} \end{matrix}]

$L$ 的对角元素均为 $1$ ， $U$ 的对角元素为其实际值。即：

L = [\begin{matrix} 1 \\ L_{21} & 1 \\ L_{31} & L_{32} & 1 \\ ⋮ & ⋮ & ⋮ & ⋱ \\ L_{i 1} & L_{i 2} & L_{i 3} & \dots & 1 \end{matrix}], U = [\begin{matrix} U_{11} & U_{12} & U_{13} & \dots & U_{1 j} \\ U_{22} & U_{23} & \dots & U_{2 j} \\ ⋱ & ⋮ & ⋮ \\ U_{i - 1, j - 1} & U_{i - 1, j} \\ U_{i j} \end{matrix}]

将 $L$ 和 $U$ 合并在同一个矩阵中的格式称为紧凑格式，记为 $(L | U)$ 。

由 $L$ 和 $U$ 合并：
紧凑格式 $(L | U)$ 中，第 $i$ 行第 $j$ 列的元素 $L_{i j}$ 对应 $L$ 中第 $i$ 行第 $j$ 列的元素， $U_{i j}$ 对应 $U$ 中第 $i$ 行第 $j$ 列的元素。
所以，
$L = [\begin{matrix} 1 \\ L_{21} & 1 \\ L_{31} & L_{32} & 1 \\ ⋮ & ⋮ & ⋱ & ⋱ \\ L_{i 1} & L_{i 2} & L_{i 3} & \dots & 1 \end{matrix}], U = [\begin{matrix} U_{11} & U_{12} & U_{13} & \dots & U_{1 j} \\ U_{22} & U_{23} & \dots & U_{2 j} \\ ⋱ & ⋮ & ⋮ \\ U_{i - 1, j - 1} & U_{i - 1, j} \\ U_{i j} \end{matrix}]$
合并为紧凑格式：
$(L | U) = [\begin{matrix} U_{11} & U_{12} & U_{13} & \dots & U_{1 j} \\ L_{21} & U_{22} & U_{23} & \dots & U_{2 j} \\ L_{31} & L_{32} & ⋱ & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋱ & U_{i - 1, j - 1} & U_{i - 1, j} \\ L_{i 1} & L_{i 2} & L_{i 3} & \dots & U_{i j} \end{matrix}]$
由系数矩阵 $A$ 直接计算：
矩阵的 LU 分解也可通过系数矩阵 $A$ 直接计算得到紧凑格式 $(L | U)$ ，也是考试中考察的重点，见下文由系数矩阵得出紧凑格式的操作方法。

先行后列，先 $U$ 后 $L$

所求得的矩阵即为紧凑格式 $(L | U)$ ，要求得 $L$ 和 $U$ ，将 $(L | U)$ 拆开即可。